#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

/**
 * Your LRUCache object will be instantiated and called as such: // 实例化和调用
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// Least Recently Used
class LRUCache
{
    typedef list<pair<int, int>>::iterator ListIt;
    int _capacity;
    unordered_map<int, ListIt> _hashmap;
    list<pair<int, int>> _LRUlist;

public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key)
    {
        auto it = _hashmap.find(key);
        if (it != _hashmap.end())
        {
            // 将该关键字移动到LRU队列头
            ListIt listit = it->second;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
            return listit->second;
        }
        else
            return -1;
    }

    void put(int key, int value)
    {
        auto it = _hashmap.find(key);
        if (it == _hashmap.end())
        {
            // 判满，如果满了逐出最久未使用的关键字
            if (_hashmap.size() == _capacity)
            {
                pair<int, int> back = _LRUlist.back();
                _hashmap.erase(back.first);
                _LRUlist.pop_back();
            }
            // 将关键字插入到LRU队列头
            _LRUlist.push_front(make_pair(key, value));
            _hashmap.insert(make_pair(key, _LRUlist.begin()));
        }
        else
        {
            // 找到了更新其value值，并将该关键字移动到LRU队列头
            ListIt listit = it->second;
            listit->second = value;
            _LRUlist.splice(_LRUlist.begin(), _LRUlist, listit);
        }
    }
};

int main()
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // returns 1
    cache.put(3, 3);              // evicts key 2
    
}